šŸ§¬ Genetic Signal GCD Analyzer

Sparse Table for Filtered Range GCD Queries

šŸ“‹ Problem Statement

You are part of a biomedical research team studying genetic marker patterns in patients over time. Each day, advanced diagnostic tools measure a genetic signal intensity, a numerical value representing the presence and dominance of certain genetic markers in a patient's blood sample.

These readings are stored as an array of integers for N consecutive days for each patient. Genetic researchers frequently submit queries like: What is the GCD of all signal values in a given period that are divisible by a specific marker threshold K.

šŸ“„ Input Format

  • First line: N (number of days, 1 ā‰¤ N ā‰¤ 20)
  • Second line: N space-separated integers (signal values, 1 ā‰¤ Signal[i] ā‰¤ 200)
  • Third line: Q (number of queries, 1 ā‰¤ Q ā‰¤ 20)
  • Next Q lines: Three integers L, R, and K
    • L, R: range of days (0 ā‰¤ L ā‰¤ R < N)
    • K: threshold - only values divisible by K are considered (1 ā‰¤ K ā‰¤ 100)

šŸ“¤ Output Format

For each query, output the GCD of all values in range [L, R] that are divisible by K.

If no value in the range is divisible by K, output 0.

šŸŽÆ Sample Test Case 1

Input: 
6
10 15 20 25 30 35
3
0 3 5
1 5 10
2 4 3
Output: 
5
10
30
Explanation:
  • Query [0, 3] with K=5:
    • Range: {10, 15, 20, 25}
    • Divisible by 5: {10, 15, 20, 25} (all)
    • GCD(10, 15, 20, 25) = 5
  • Query [1, 5] with K=10:
    • Range: {15, 20, 25, 30, 35}
    • Divisible by 10: {20, 30}
    • GCD(20, 30) = 10
  • Query [2, 4] with K=3:
    • Range: {20, 25, 30}
    • Divisible by 3: {30}
    • GCD(30) = 30

šŸŽÆ Sample Test Case 2

Input: 
7
12 18 24 30 36 42 48
3
0 6 6
2 5 3
1 4 5
Output: 
6
6
30

šŸ§  Sparse Table for Filtered GCD Queries

This problem combines range querying with filtering. We need to find the GCD of values in a range that satisfy a divisibility condition. While sparse tables work well for GCD (since GCD is associative), the filtering adds complexity.

šŸ“Š Approach

Since the threshold K varies per query and we can't precompute for all possible K values efficiently, we use a hybrid approach:

  1. Build a sparse table for standard range GCD queries
  2. For each query, filter values in the range that are divisible by K
  3. Compute GCD of the filtered values

šŸ”§ Building Sparse Table (for GCD)

// GCD function
int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

// Initialize for length 1 (2^0)
for (int i = 0; i < n; i++) {
    sparse[i][0] = signal[i];
}

// Build for increasing powers of 2
for (int j = 1; (1 << j) <= n; j++) {
    for (int i = 0; i + (1 << j) <= n; i++) {
        sparse[i][j] = gcd(sparse[i][j-1],
                          sparse[i + (1 << (j-1))][j-1]);
    }
}

šŸ” Query Processing

int queryFilteredGCD(int L, int R, int K) {
    vector filtered;

    // Filter values divisible by K
    for (int i = L; i <= R; i++) {
        if (signal[i] % K == 0) {
            filtered.push_back(signal[i]);
        }
    }

    // If no values match, return 0
    if (filtered.empty()) {
        return 0;
    }

    // Compute GCD of filtered values
    int result = filtered[0];
    for (int i = 1; i < filtered.size(); i++) {
        result = gcd(result, filtered[i]);
        if (result == 1) break;  // Optimization
    }

    return result;
}

āš” Complexity Analysis

Build: O(n log n) Query: O(n) for filtering + O(m log V) for GCD Space: O(n log n)
  • Build: O(n log n) - construct sparse table
  • Query: O(n) to filter + O(m log V) to compute GCD of m filtered values
  • Note: The filtering step dominates, making this O(n) per query

šŸ’” GCD Properties

  • Associative: GCD(a, GCD(b, c)) = GCD(GCD(a, b), c)
  • Commutative: GCD(a, b) = GCD(b, a)
  • Identity: GCD(a, 0) = a
  • Divisibility: If all numbers are divisible by K, their GCD is also divisible by K
  • Range Property: GCD of numbers ā‰¤ minimum number in the set

šŸŽÆ Example Walkthrough

Signals: [10, 15, 20, 25, 30], Query [0, 4] with K=5

Step 1: Filter values divisible by 5
  10 % 5 = 0 āœ“ ā†’ Include 10
  15 % 5 = 0 āœ“ ā†’ Include 15
  20 % 5 = 0 āœ“ ā†’ Include 20
  25 % 5 = 0 āœ“ ā†’ Include 25
  30 % 5 = 0 āœ“ ā†’ Include 30
  Filtered: [10, 15, 20, 25, 30]

Step 2: Compute GCD iteratively
  GCD(10, 15) = 5
  GCD(5, 20) = 5
  GCD(5, 25) = 5
  GCD(5, 30) = 5

Result: 5

šŸ“Š Input Configuration

Normal
In Range
Divisible by K
Used in GCD
Not Divisible

šŸ§¬ Genetic Signal Array

šŸ—‚ļø Sparse Table (GCD)

āš™ļø Current Operation

Ready to build table...
Operation log will appear here...